COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00007 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a25.tex[154,phy] \today\hfill}

\bigskip
If $C$ is a class of machines (e.g., deterministic machines with finitely
many control states and one tape, i.e., Turing machines), then $U$ is
a {\sl universal\/} machine for~$C$ if, for each machine~$M$ of~$C$,
there is a code, or program, $p=P(M)$, for which $U$ on input~$px$ simulates
what $M$ does on input~$x$. Typically, $p$~is some sort of list of
4~tuples $\langle q↓i,t↓j,a↓k,q↓l\rangle$, each of which says that
if $M$ is in state~$q↓i$ and test~$t↓j$ is true, $M$~performs action~$a↓k$
and enters state~$q↓l$. If $C$ is the class of Turing machines, normally
$t↓j$ is symbolized by 0 or~1, testing whether the tape character is~0
($=$~blank) or~1 respectively; normally the actions are symbolized
0, 1, $L$, and~$R$, for writing a 0 or~1, moving left or right.

It is a routine programming exercise to design a universal Turing machine,
i.e., a~Turing machine which is universal for the class of Turing machines.
Similarly, there are universal 2-stack and 2-counter machines.

\bigskip
\noindent{\bf Theorem.} (Undecidability of the Halting Problem.)

If $U$ is a universal Turing machine, there is no algorithm executable by
a~Turing machine to determine for all~$x$ whether $U$ halts on input~$x$.

\smallskip\noindent
{\bf Proof:} Suppose there were such an algorithm, $H(x)$. Then we could
construct a Turing machine~$M$, using a machine for $H$ as a component,
which, on input~$p$, does this:

\smallskip\halign{\qquad\qquad\lft{\tt #}\cr
IF H(pp) THEN\cr
\qq WHILE 1>0 DO\cr
\qq PRINT 0\cr
ELSE Print 1\cr}

\smallskip\noindent
Let $q$ be the program for the
aforesaid machine~$M$, and let's see what $M$ does on input~$q$. There are
two cases, according as $M$~halts on input~$q$ or not.

\smallskip
{\bf Case 1:} $M$ halts on input~$q$, then $U(qq)$ halts, and $H(qq)$
is true, so~$M$, on input~$q$, takes the branch which makes it run forever;
contradiction.

\smallskip
{\bf Case 2:} $M$ runs forever on input $q$. Then $U(qq)$ also runs forever,
and $H(qq)$ is false,
so~$M$, on input~$q$, takes the branch which halts. Again, a~contradiction.
The only weak point in the construction of $M$ is the assumption that there
is an algorithm for~$H$.



\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 23, 1984

\bye